Graph Mining on Walmart and Facebook Data¶
In [9]:
# Retrieve csv file from google drive by mapping the folder from google drive.
# Must be done each time session expires.
from google.colab import drive
drive.mount('/content/drive')
Import networkx¶
Installation information available here - https://networkx.org/documentation/stable/install.html¶
!pip install networkx¶
Find tutorials, references and background of networkx here - https://networkx.org/documentation/stable/index.html¶
In [10]:
import networkx as nx
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
from scipy import stats
import csv
In [11]:
np.random.seed(123456)
Graph drawing and information with a graph embedded in networkx¶
In [12]:
# Retrieve and safe a copy the karate_club_graph()
kc_g = nx.karate_club_graph()
In [13]:
# Show basic graph information
print(nx.info(kc_g))
In [14]:
# help(nx.draw)
In [15]:
# nx.draw is a simple graph drawing function that utilizes Matplotlib
# sacle up the figsize
plt.figure(figsize=(10,8))
nx.draw(kc_g, with_labels=True, node_color='lime')
In [16]:
# help(nx.draw_networkx)
In [17]:
# Draw graphs using nx.draw_networkx
plt.figure(figsize=(10,10))
nx.draw_networkx(kc_g, with_labels=True, node_color='red')
In [18]:
plt.figure(figsize=(10,10))
nx.draw_networkx(kc_g, pos = nx.spring_layout(kc_g), with_labels=True)
In [19]:
plt.figure(figsize=(10,10))
nx.draw_spring(kc_g, with_labels=True, node_color='gold')
plt.show()
In [20]:
plt.figure(figsize=(10,10))
g_layout = nx.circular_layout(kc_g)
nx.draw_networkx(kc_g, g_layout, with_labels=True, node_color='gold')
In [21]:
plt.figure(figsize=(10,10))
nx.draw_circular(kc_g, with_labels=True)
plt.show()
In [22]:
# nx.kamada_kawai is also a nice node positioning algorithm
plt.figure(figsize=(10,10))
g_layout = nx.kamada_kawai_layout(kc_g)
nx.draw_networkx(kc_g, g_layout, with_labels=True, node_color='gold')
Edge and Node Reporting¶
In [23]:
# It is not practical to show all nodes and node information this way
print(kc_g.nodes)
In [24]:
kc_g.nodes('club')
Out[24]:
In [25]:
kc_g.nodes('club')[0]
Out[25]:
In [26]:
print("Node club\n")
for v in kc_g:
print(f"{v:4} {kc_g.nodes('club')[v]}")
In [27]:
print(f'Number of nodes: {kc_g.number_of_nodes()}, Number of edges: {kc_g.number_of_edges()}')
In [28]:
# It is not practical to show all of the edges this way
kc_g.edges
Out[28]:
In [29]:
print('Graph edges:\n')
for e in kc_g.edges: print(e)
Adjacency matrix¶
In [30]:
#help(nx.adj_matrix)
In [31]:
# The default storage format of adjacency matrices is the sparse matrix format
print(nx.adj_matrix(kc_g))
In [32]:
# Show an adjacency matrix in a dense matrix format
print(nx.adj_matrix(kc_g).todense())
Node Degrees¶
In [33]:
# It is not practical to show all node degrees this way
kc_g.degree
Out[33]:
In [34]:
kc_g.degree(0)
Out[34]:
In [35]:
print("Node Degree\n")
for v in kc_g.nodes:
print(f"{v:4} {kc_g.degree(v):6}")
# right-justified each column
In [36]:
# help(nx.degree_histogram)
In [37]:
nx.degree_histogram(kc_g)
# Frequency (# of nodes) of a degree - 0, 1, 2, up to 17
Out[37]:
In [38]:
# Draw a bar graph of number of Node Degree Distribution
# create x and y values of each bar
y_axis = nx.degree_histogram(kc_g)
x_axis = list(range(0,len(y_axis)))
# Draw bars using y_axis and x_axis
plt.bar(x_axis, y_axis, color = 'purple')
# draw tick labels
plt.xticks(x_axis)
plt.yticks(list(range(0,max(y_axis)+1)))
# Add title and axis names
plt.title(f'Node Degree Distributation in {kc_g.name}')
plt.xlabel('Degree')
plt.ylabel('Frequency')
plt.show()
In [39]:
degrees = nx.degree_histogram(kc_g)
y_axis = [i/sum(degrees) for i in degrees]
# x_axis = list(range(0,len(y_axis)))
plt.bar(x_axis, y_axis, color = 'purple')
# Draw axis labels
plt.xticks(x_axis)
plt.yticks([0.0,0.1,0.2,0.3,0.4,0.5])
# Add title and axis names
plt.title(f'Degree Percentage Distributation in {kc_g.name}')
plt.xlabel('Degree')
plt.ylabel('Percentage')
plt.ylim(0,0.5)
plt.show()
Using node information to draw nodes¶
In [40]:
plt.figure(figsize=(10,9))
plt.title(f'Circular Plot of {kc_g.name} Showing Node Degrees via Node Colors and Sizes', fontsize = 14)
degree_color = [kc_g.degree(v) for v in kc_g]
degree_size = [100*kc_g.degree(v) for v in kc_g]
nx.draw_circular(kc_g, node_color = degree_color , node_size = (degree_size),font_color = 'r', with_labels=True, cmap = plt.cm.Greens)
# https://matplotlib.org/3.1.0/tutorials/colors/colormaps.html
plt.show()
Distance Measures¶
In [41]:
#help(nx.shortest_path)
In [42]:
nx.shortest_path(kc_g,0,33)
Out[42]:
In [43]:
nx.shortest_path_length(kc_g,0,33)
Out[43]:
In [44]:
nx.shortest_path(kc_g,6,33)
Out[44]:
In [45]:
nx.shortest_path(kc_g,6,33)
Out[45]:
In [46]:
nx.shortest_path_length(kc_g,6,33)
Out[46]:
In [47]:
nx.shortest_path(kc_g,33)
Out[47]:
In [48]:
nx.shortest_path_length(kc_g,33)
Out[48]:
In [49]:
nx.average_shortest_path_length(kc_g)
Out[49]:
In [50]:
nx.eccentricity(kc_g)
Out[50]:
In [51]:
nx.diameter(kc_g)
Out[51]:
In [52]:
nx.radius(kc_g)
Out[52]:
In [53]:
nx.periphery(kc_g)
Out[53]:
In [54]:
nx.center(kc_g)
Out[54]:
Clustering¶
Complete Graph¶
In [55]:
# Create a 4-node complete graph
G = nx.complete_graph(4)
nx.draw_circular(G, with_labels=True)
In [56]:
# help(nx.clustering)
In [57]:
nx.clustering(G)
Out[57]:
In [58]:
nx.average_clustering(G)
Out[58]:
In [59]:
nx.clustering(kc_g)
Out[59]:
In [60]:
round(nx.average_clustering(kc_g),2)
Out[60]:
Weighted Undirected Graph - Support percent of two co-purchased depts¶
In [61]:
# help(nx.read_weighted_edgelist)
In [62]:
# Load a graph from a list of edges in a csv file
copur_sup_g = nx.read_weighted_edgelist('/content/drive/My Drive/Walmart_8_depts_support_edges.csv', delimiter =",")
In [63]:
copur_sup_g.name = 'Walmart Copurchase Department Support Graph'
In [64]:
plt.figure(figsize =(12, 9))
plt.title(copur_sup_g.name, fontsize=16, color= 'b')
nx.draw_circular(copur_sup_g, with_labels = True, node_color='gold',node_size=1000, font_size=12,font_color = 'b')
In [65]:
print(nx.info(copur_sup_g))
In [66]:
copur_sup_g.nodes
Out[66]:
In [67]:
copur_sup_g.edges
Out[67]:
Get and use weights¶
In [68]:
print(copur_sup_g.edges.data('weight'))
In [69]:
for (u, v, wt) in copur_sup_g.edges.data('weight'):
print(f"({u}, {v}, {wt:.3})")
In [70]:
# adjacency matrix of a weighted graph shows weight values instead of zeros and ones
nx.adj_matrix(copur_sup_g).todense()
Out[70]:
In [71]:
print("Node Degree\n")
for v in copur_sup_g.nodes:
print(f'{v:25} {copur_sup_g.degree(v):6}')
# right-justified each column
In [72]:
nx.degree_histogram(copur_sup_g)
Out[72]:
In [73]:
# Draw a bar graph of number of Node Degree Distribution
# create x and y values of each bar
y_axis = nx.degree_histogram(copur_sup_g)
x_axis = list(range(0,len(y_axis)))
# Draw bars using y_axis and x_axis
plt.bar(x_axis, y_axis, color = 'purple')
# draw tick labels
plt.xticks(x_axis)
plt.yticks(list(range(0,max(y_axis)+1)))
# Add title and axis names
plt.title(f'Node Degree Distributation in {copur_sup_g.name}')
plt.xlabel('Degree')
plt.ylabel('Frequency')
plt.show()
In [74]:
degrees = nx.degree_histogram(copur_sup_g)
y_axis = [i/sum(degrees) for i in degrees]
# x_axis = list(range(0,len(y_axis)))
plt.bar(x_axis, y_axis, color = 'purple')
# Draw axis labels
plt.xticks(x_axis)
plt.yticks([0.0,0.1,0.2,0.3,0.4,0.5])
# Add title and axis names
plt.title(f'Degree Percentage Distributation in {copur_sup_g.name}')
plt.xlabel('Degree')
plt.ylabel('Percentage')
plt.ylim(0,0.5)
plt.show()
In [75]:
plt.figure(figsize=(10,10))
plt.title(f'Circular Plot of {copur_sup_g.name} Showing Weights via edge_width', fontsize = 14)
degree_color = [copur_sup_g.degree(v) for v in copur_sup_g]
degree_size = [200*copur_sup_g.degree(v) for v in copur_sup_g]
edge_width = [50*(copur_sup_g[u][v]['weight']) for u,v in copur_sup_g.edges]
nx.draw_circular(copur_sup_g, width=edge_width,edge_color = 'orange',node_color = degree_color , node_size = (degree_size), with_labels=True, cmap = plt.cm.Oranges)
plt.show()
In [76]:
nx.shortest_path(copur_sup_g)
Out[76]:
In [77]:
path_ct = 0
sum_shortest_len = 0
for v1 in copur_sup_g.nodes:
for v2 in copur_sup_g.nodes:
if v1 != v2:
path_ct +=1
sum_shortest_len +=nx.shortest_path_length(copur_sup_g,v1,v2)
print(f"({v1}, {v2}, {nx.shortest_path_length(copur_sup_g,v1,v2)})")
In [78]:
print('average shortest path length = ', sum_shortest_len/path_ct)
In [79]:
nx.average_shortest_path_length(copur_sup_g)
Out[79]:
In [80]:
nx.eccentricity(copur_sup_g)
Out[80]:
In [81]:
nx.diameter(copur_sup_g)
Out[81]:
In [82]:
nx.radius(copur_sup_g)
Out[82]:
In [83]:
nx.periphery(copur_sup_g)
Out[83]:
In [84]:
nx.center(copur_sup_g)
Out[84]:
In [85]:
nx.clustering(copur_sup_g)
Out[85]:
In [86]:
nx.average_clustering(copur_sup_g)
Out[86]:
Directed Graph - Confidence of two co-purchased depts¶
In [87]:
# Load a graph from an input csv file
copur_conf_g = nx.read_weighted_edgelist('/content/drive/My Drive/Walmart_8_depts_confidence_edges.csv', delimiter =",",create_using=nx.DiGraph)
In [88]:
copur_conf_g.name = 'Walmart Copurchase Department Confidence Graph'
In [89]:
# g_layout = nx.circular_layout(copur_conf_g)
plt.figure(figsize =(12, 9))
plt.title(copur_conf_g.name, fontsize=16)
nx.draw_circular(copur_conf_g, with_labels = True, node_color='gold',node_size=1000, font_size=12, edge_color = 'b')
In [90]:
print(nx.info(copur_conf_g))
In [91]:
copur_conf_g.nodes
Out[91]:
In [92]:
copur_conf_g.edges
Out[92]:
In [93]:
for (u, v, wt) in copur_conf_g.edges.data('weight'):
print(f"({u}, {v}, {wt:.3})")
In [94]:
nx.adj_matrix(copur_conf_g).todense()
Out[94]:
In [95]:
plt.figure(figsize=(10,10))
plt.title(f'Circular Plot of {copur_sup_g.name} Showing Weights via edge_width', fontsize = 14)
degree_color = [copur_conf_g.degree(v) for v in copur_conf_g]
degree_size = [200*copur_conf_g.degree(v) for v in copur_conf_g]
edge_width = [10*(copur_conf_g[u][v]['weight']) for u,v in copur_conf_g.edges]
nx.draw_circular(copur_conf_g, width=edge_width,edge_color = 'orange',node_color = degree_color , node_size = (degree_size), with_labels=True, cmap = plt.cm.Oranges)
plt.show()
In [96]:
print("Node OutDegree InDegree Degree\n")
for v in copur_sup_g.nodes:
print(f'{v:26}{copur_conf_g.out_degree(v):9}{copur_conf_g.in_degree(v):9}{copur_conf_g.degree(v):7}')
# right-justified each column
In [97]:
nx.degree_histogram(copur_conf_g)
# The same as copur_sup_g. No existing functions to generate distribution of in and out degrees.
Out[97]:
In [98]:
# Draw a bar graph of number of Node Degree Distribution
# create x and y values of each bar
y_axis = nx.degree_histogram(copur_conf_g)
x_axis = list(range(0,len(y_axis)))
# Draw bars using y_axis and x_axis
plt.bar(x_axis, y_axis, color = 'purple')
# draw tick labels
plt.xticks(x_axis)
plt.yticks(list(range(0,max(y_axis)+1)))
# Add title and axis names
plt.title(f'Node Degree Distributation in {copur_conf_g.name}')
plt.xlabel('Degree')
plt.ylabel('Frequency')
plt.show()
In [99]:
degrees = nx.degree_histogram(copur_conf_g)
y_axis = [i/sum(degrees) for i in degrees]
# x_axis = list(range(0,len(y_axis)))
plt.bar(x_axis, y_axis, color = 'purple')
# Draw axis labels
plt.xticks(x_axis)
plt.yticks([0.0,0.1,0.2,0.3,0.4,0.5])
# Add title and axis names
plt.title(f'Degree Percentage Distributation in {copur_conf_g.name}')
plt.xlabel('Degree')
plt.ylabel('Percentage')
plt.ylim(0,0.5)
plt.show()
In [100]:
nx.shortest_path(copur_conf_g)
Out[100]:
In [101]:
nx.shortest_path(copur_conf_g,source='MEAT - FRESH & FROZEN')
Out[101]:
In [102]:
nx.shortest_path_length(copur_conf_g,'MEAT - FRESH & FROZEN', 'PRODUCE')
Out[102]:
In [103]:
nx.shortest_path(copur_conf_g,source='DAIRY')
Out[103]:
In [104]:
nx.shortest_path(copur_conf_g,target='DAIRY')
Out[104]:
In [105]:
nx.average_shortest_path_length(copur_conf_g)
Out[105]:
diameter, radius, eccentricity, periphery, center are not available for non-strongly-connected graph¶
Ref: https://en.wikipedia.org/wiki/Strongly_connected_component
In [106]:
nx.is_strongly_connected(copur_conf_g)
Out[106]:
In [107]:
nx.clustering(copur_conf_g)
Out[107]:
In [108]:
nx.average_clustering(copur_conf_g)
Out[108]:
Facebook Example - Undirected, Unweighted¶
Add attributes to nodes¶
In [109]:
FBGraph = nx.read_weighted_edgelist('/content/drive/My Drive//FacebookEdges_limited_A7S2.csv', delimiter =",")
FBGraph.name = 'Facebook Graph of Randomly Sampled Users'
In [110]:
print(nx.info(FBGraph))
In [111]:
plt.figure(figsize=(25,25))
# g_layout = nx.kamada_kawai_layout(FBGraph)
# nx.draw_networkx(FBGraph,g_layout, with_labels = True)
# nx.draw_circular(FBGraph, with_labels = True, font_size=14)
nx.draw_networkx(FBGraph, with_labels = True)
# plt.axis('off')
# plt.tight_layout()
plt.show()
In [112]:
with open('/content/drive/My Drive/FacebookNodes_limited_A7S2.csv') as csvfile:
nodereader = csv.reader(csvfile, delimiter=',')
for row in nodereader:
if(row[0] in FBGraph.nodes):
FBGraph.nodes[row[0]]['name'] = row[1]
FBGraph.nodes[row[0]]['gender'] = row[2]
FBGraph.nodes[row[0]]['age'] = int(row[3])
FBGraph.nodes[row[0]]['country'] = row[4]
In [113]:
FBGraph.nodes.data('gender')
Out[113]:
In [114]:
FB_name_Graph = nx.relabel_nodes(FBGraph, nx.get_node_attributes(FBGraph, 'name'))
In [115]:
plt.figure(figsize=(25,25))
nx.draw_networkx(FB_name_Graph, with_labels = True)
# plt.axis('off')
plt.tight_layout()
plt.show()
In [116]:
plt.figure(figsize=(25,25))
nx.draw_circular(FB_name_Graph, with_labels = True)
# plt.axis('off')
# plt.tight_layout()
plt.show()
In [117]:
print(nx.info(FB_name_Graph))
# As we will see later, FB_name_Graph collapsed different nodes with the same names in FBGraph
# To avoid loss of information, we continue to use FBGraph
Color the nodes by the country attribute¶
In [118]:
# Use set to get unique countries only
set(nx.get_node_attributes(FBGraph, 'country').values())
Out[118]:
In [119]:
colorMap = {'Belgium':'black', 'Germany':'gold','Canada':'r', 'Costa Rica':'brown','Japan':'maroon', 'Now Coalinga':'purple',
'Mexico':'olive','Philippines':'blue','Poland':'yellow','Singapore':'orange', 'United Kingdom':'green', 'United States':'royalblue'}
In [120]:
node_color = [colorMap[FBGraph.nodes[v]['country']] for v in FBGraph.nodes()]
plt.figure(figsize=(10,10))
nx.draw(FBGraph, with_labels = False, node_color=node_color)
In [121]:
nx.adj_matrix(FBGraph).todense()
Out[121]:
In [122]:
# Draw a bar graph of number of Node Degree Distribution
# create x and y values of each bar
y_axis = nx.degree_histogram(FBGraph)
x_axis = list(range(0,len(y_axis)))
# Draw bars using y_axis and x_axis
plt.bar(x_axis, y_axis, color = 'purple')
# draw tick labels
plt.xticks(x_axis)
plt.yticks(list(range(0,max(y_axis)+1)))
# Add title and axis names
plt.title(f'Node Degree Distributation in {FBGraph.name}')
plt.xlabel('Degree')
plt.ylabel('Frequency')
plt.show()
In [123]:
degrees = nx.degree_histogram(FBGraph)
y_axis = [i/sum(degrees) for i in degrees]
# x_axis = list(range(0,len(y_axis)))
plt.bar(x_axis, y_axis, color = 'purple')
# Draw axis labels
plt.xticks(x_axis)
plt.yticks([0.00,0.05,0.10,0.15,0.20,0.25])
# Add title and axis names
plt.title(f'Degree Percentage Distributation in {FBGraph.name}')
plt.xlabel('Degree')
plt.ylabel('Percentage')
plt.ylim(0,0.25)
plt.show()
In [124]:
nx.shortest_path(FBGraph,'99','163')
Out[124]:
In [125]:
nx.shortest_path(FBGraph,'99','471')
Out[125]:
In [126]:
nx.shortest_path_length(FBGraph,source='99')
Out[126]:
In [127]:
nx.average_shortest_path_length(FBGraph)
Out[127]:
In [128]:
nx.diameter(FBGraph)
Out[128]:
In [129]:
nx.radius(FBGraph)
Out[129]:
In [130]:
nx.periphery(FBGraph)
Out[130]:
In [131]:
nx.center(FBGraph)
Out[131]:
In [132]:
nx.average_clustering(FBGraph)
Out[132]:
Create a pandas dataframe of nodal information¶
In [133]:
df = pd.DataFrame(index=FBGraph.nodes())
df['name'] = pd.Series(nx.get_node_attributes(FBGraph, 'name'))
df['gender'] = pd.Series(nx.get_node_attributes(FBGraph, 'gender'))
df['age'] = pd.Series(nx.get_node_attributes(FBGraph, 'age'))
df['country'] = pd.Series(nx.get_node_attributes(FBGraph, 'country'))
df['degree'] = pd.Series(dict(FBGraph.degree()))
df['eccentricity'] = pd.Series(nx.eccentricity(FBGraph))
df['clustering'] = pd.Series(nx.clustering(FBGraph))
df.head(20)
Out[133]:
In [134]:
# Create another data frame from FB_name_Graph for comparison
df1 = pd.DataFrame(index=FB_name_Graph.nodes())
df1['name'] = pd.Series(nx.get_node_attributes(FB_name_Graph, 'name'))
df1['gender'] = pd.Series(nx.get_node_attributes(FB_name_Graph, 'gender'))
df1['age'] = pd.Series(nx.get_node_attributes(FB_name_Graph, 'age'))
df1['country'] = pd.Series(nx.get_node_attributes(FB_name_Graph, 'country'))
df1['degree'] = pd.Series(dict(FB_name_Graph.degree()))
df1['eccentricity'] = pd.Series(nx.eccentricity(FB_name_Graph))
df1['clustering'] = pd.Series(nx.clustering(FB_name_Graph))
df1
Out[134]:
In [135]:
# Show duplicated users
df[df.name.duplicated()]
Out[135]:
In [136]:
df[df['name'].str.match('Hamtaro')]
Out[136]:
In [137]:
df1[df1['name'].str.match('Hamtaro')]
Out[137]:
In [138]:
df.degree.sort_values(ascending=False)
Out[138]:
In [139]:
# For comparison, you can see the changes in degree count between the two FB graphs
# Continue with df
df1.degree.sort_values(ascending=False)
Out[139]:
In [140]:
df.clustering.sort_values(ascending=False)
Out[140]:
In [141]:
df.eccentricity.sort_values(ascending=False)
Out[141]:
In [142]:
df.age.sort_values(ascending=False)
Out[142]:
Module 8¶
Node Importance and edge_betweenness_centrality¶
Complete graph, and other simple graphs¶
In [143]:
# help(nx.degree_centrality)
In [144]:
# G is a complete graph
G.degree
Out[144]:
In [145]:
nx.degree_centrality(G)
# Each node in a complete graph has the maximum # of degrees
Out[145]:
In [146]:
# help(nx.closeness_centrality)
In [147]:
nx.closeness_centrality(G)
# The average distance to other nodes and the inverse of this average is 1
Out[147]:
In [148]:
# help(nx.betweenness_centrality)
In [149]:
nx.betweenness_centrality(G)
# Each pair of other nodes in a complete graph are connected to each other.
# None of their shortest paths for other pairs of nodes pass through a focal node.
Out[149]:
In [150]:
# help(nx.edge_betweenness_centrality)
In [151]:
nx.edge_betweenness_centrality(G)
# In a complete graph, the lowest possible edge_betweeness is 1/6,
# because the total number of shortest paths, 6, is als the total number of edges.
Out[151]:
In [152]:
u_g = nx.Graph()
u_g.add_node(0)
u_g.add_edge(0, 1)
u_g.add_edge(1, 2)
u_g.add_edge(2, 3)
u_g.add_edges_from([(2,0),(3, 1)])
nx.draw(u_g, with_labels=True, node_color='brown',font_color='white')
In [153]:
d_g = nx.DiGraph()
d_g.add_node(0)
d_g.add_edge(0, 1)
d_g.add_edge(1, 2)
d_g.add_edge(2, 3)
d_g.add_edges_from([(2, 0), (3, 1)])
nx.draw(d_g, with_labels=True, node_color='brown',font_color='white')
In [154]:
print(u_g.degree,'\n',d_g.degree,'\n')
print(nx.degree_centrality(u_g),'\n',nx.degree_centrality(d_g))
In [155]:
print(list(nx.shortest_path_length(u_g)),'\n',list(nx.shortest_path_length(d_g)),'\n')
# In u_g, average shortest path lengths to other nodes is 1 for nodes 1 and 2
# In u_g, aAverage shortest path lengths to other nodes is 4/3 for nodes 0 and 3
# In d_g, average shortest path lengths to other nodes: 4/3 for node 1, 3/2 for 2
# In d_g, aAverage shortest path lengths to other nodes is 2 for nodes 0 and 3
print(nx.closeness_centrality(u_g),'\n',nx.closeness_centrality(d_g))
In [156]:
print(nx.betweenness_centrality(u_g),'\n',nx.betweenness_centrality(d_g))
In [157]:
nx.edge_betweenness_centrality(u_g)
# Node betweenness may affect edge_betweenness
Out[157]:
In [158]:
nx.edge_betweenness_centrality(d_g)
# Node betweenness may affect edge_betweenness
Out[158]:
Karate_club, co_purchase and facebook graphs¶
In [159]:
kc_df = pd.DataFrame(index=kc_g.nodes())
kc_df['club'] = pd.Series(nx.get_node_attributes(kc_g, 'club'))
kc_df['degree'] = pd.Series(dict(kc_g.degree()))
kc_df['eccentricity'] = pd.Series(nx.eccentricity(kc_g))
kc_df['clustering'] = pd.Series(nx.clustering(kc_g))
kc_df['degree_centrality'] = pd.Series(nx.degree_centrality(kc_g))
kc_df['closeness'] = pd.Series(nx.closeness_centrality(kc_g))
kc_df['betweenness'] = pd.Series(nx.betweenness_centrality(kc_g))
kc_df
Out[159]:
In [160]:
nx.edge_betweenness_centrality(kc_g)
Out[160]:
In [161]:
kc_df.drop('club',axis=1).corr()
Out[161]:
In [162]:
copur_sup_df = pd.DataFrame(index=copur_sup_g.nodes())
copur_sup_df['degree'] = pd.Series(dict(copur_sup_g.degree()))
copur_sup_df['eccentricity'] = pd.Series(nx.eccentricity(copur_sup_g))
copur_sup_df['clustering'] = pd.Series(nx.clustering(copur_sup_g))
copur_sup_df['degree_centrality'] = pd.Series(nx.degree_centrality(copur_sup_g))
copur_sup_df['closeness'] = pd.Series(nx.closeness_centrality(copur_sup_g))
copur_sup_df['betweenness'] = pd.Series(nx.betweenness_centrality(copur_sup_g))
copur_sup_df
Out[162]:
In [163]:
nx.edge_betweenness_centrality(copur_sup_g)
Out[163]:
In [164]:
copur_sup_df.corr()
Out[164]:
In [165]:
copur_conf_df = pd.DataFrame(index=copur_conf_g.nodes())
copur_conf_df['degree'] = pd.Series(dict(copur_conf_g.degree()))
copur_conf_df['out_degree'] = pd.Series(dict(copur_conf_g.out_degree()))
copur_conf_df['in_degree'] = pd.Series(dict(copur_conf_g.in_degree()))
# copur_conf_df['eccentricity'] = pd.Series(nx.eccentricity(copur_conf_g))
copur_conf_df['clustering'] = pd.Series(nx.clustering(copur_conf_g))
copur_conf_df['degree_cen'] = pd.Series(nx.degree_centrality(copur_conf_g))
copur_conf_df['out_degree_cen'] = pd.Series(nx.out_degree_centrality(copur_conf_g))
copur_conf_df['in_degree_cen'] = pd.Series(nx.in_degree_centrality(copur_conf_g))
copur_conf_df['closeness'] = pd.Series(nx.closeness_centrality(copur_conf_g))
copur_conf_df['betweenness'] = pd.Series(nx.betweenness_centrality(copur_conf_g))
copur_conf_df
Out[165]:
In [166]:
nx.edge_betweenness_centrality(copur_conf_g)
Out[166]:
In [167]:
copur_conf_df.corr()
Out[167]:
In [168]:
fb_df = pd.DataFrame(index=FBGraph.nodes())
df['name'] = pd.Series(nx.get_node_attributes(FBGraph, 'name'))
fb_df['gender'] = pd.Series(nx.get_node_attributes(FBGraph, 'gender'))
fb_df['age'] = pd.Series(nx.get_node_attributes(FBGraph, 'age'))
fb_df['country'] = pd.Series(nx.get_node_attributes(FBGraph, 'country'))
fb_df['degree'] = pd.Series(dict(FBGraph.degree()))
fb_df['eccentricity'] = pd.Series(nx.eccentricity(FBGraph))
fb_df['clustering'] = pd.Series(nx.clustering(FBGraph))
fb_df['degree_cen'] = pd.Series(nx.degree_centrality(FBGraph))
fb_df['closeness'] = pd.Series(nx.closeness_centrality(FBGraph))
fb_df['betweenness'] = pd.Series(nx.betweenness_centrality(FBGraph))
# explroe edge_betweenness_centrality of some of the edges if interested
print(fb_df.index)
fb_df
Out[168]:
In [169]:
# Check out edge_betweenness_centrality of all edges of FBGraph if you are interested
# nx.edge_betweenness_centrality(FBGraph)
In [170]:
fb_df.drop({'gender','country'},axis=1).corr()
Out[170]:
Link Prediction - Edge Attachment Measurements¶
In [171]:
# help(nx.common_neighbors)
In [172]:
list(nx.common_neighbors(G,0,1))
Out[172]:
In [173]:
list(nx.common_neighbors(u_g,0,1))
Out[173]:
In [174]:
s='pair'
In [175]:
print('In G:\n')
print(f'{s:6}|no of comm neighbors|list of comm neighbors\n')
for edge in G.edges:
print(f'{edge[0]} - {edge[1]} |{len(list(nx.common_neighbors(G,edge[0],edge[1]))):20}| {list(nx.common_neighbors(G,edge[0],edge[1]))}')
print('\n In u_g:\n')
print(f'{s:6}|no of comm neighbors|list of comm neighbors\n')
for edge in u_g.edges:
print(f'{edge[0]} - {edge[1]} |{len(list(nx.common_neighbors(u_g,edge[0],edge[1]))):20}| {list(nx.common_neighbors(u_g,edge[0],edge[1]))}')
In [176]:
# help(nx.common_neighbor_centrality)
In [177]:
# By default, common_neighbor_centrality reports edge attachment scores for edges that don't exist yet
list(nx.common_neighbor_centrality(G))
Out[177]:
In [178]:
# Provide a list of edges in nx.common_neighbor_centrality()
list(nx.common_neighbor_centrality(G,G.edges))
Out[178]:
In [179]:
print('In u_g:\n\n common_neighbor_centrality of non_edges\n',\
list(nx.common_neighbor_centrality(u_g,list(nx.non_edges(u_g)))),'\n')
print('common_neighbor_centrality of existing edges\n',\
list(nx.common_neighbor_centrality(u_g, u_g.edges)))
In [180]:
list(nx.common_neighbor_centrality(u_g, u_g.edges))
Out[180]:
In [181]:
print('In copur_sup_G:\n')
print(f'{s:46}|no of comm neighbors|list of comm neighbors\n')
for edge in copur_sup_g.edges:
print(f'{edge[0]:21} - {edge[1]:21} |{len(list(nx.common_neighbors(copur_sup_g,edge[0],edge[1]))):20}|{list(nx.common_neighbors(copur_sup_g,edge[0],edge[1]))}')
In [182]:
list(nx.common_neighbor_centrality(copur_sup_g,copur_sup_g.edges))
Out[182]:
In [183]:
for edge in nx.non_edges(copur_sup_g):
print(edge[0],edge[1],len(list(nx.common_neighbors(copur_sup_g,edge[0],edge[1]))))
In [184]:
list(nx.common_neighbor_centrality(copur_sup_g))
Out[184]:
Jaccard Coefficient¶
In [185]:
# help(nx.jaccard_coefficient)
In [186]:
list(nx.jaccard_coefficient(G))
Out[186]:
In [187]:
list(nx.jaccard_coefficient(G, G.edges))
Out[187]:
In [188]:
list(nx.jaccard_coefficient(u_g, u_g.edges))
Out[188]:
In [189]:
list(nx.jaccard_coefficient(u_g))
Out[189]:
In [190]:
list(nx.jaccard_coefficient(copur_sup_g, copur_sup_g.edges))
Out[190]:
In [191]:
list(nx.jaccard_coefficient(copur_sup_g))
Out[191]:
In [192]:
kc_no_df = pd.DataFrame(list(nx.common_neighbor_centrality(kc_g)),columns=['node1', 'node2','cn_cen'])
kc_no_df
Out[192]:
In [193]:
preds = nx.jaccard_coefficient(kc_g)
preds_p = []
for u, v, p in preds:
preds_p.append(p)
kc_no_df['jaccard'] = pd.Series(preds_p)
y_col = pd.Series(0, name='HasEdge').repeat(len(kc_no_df)).reset_index(drop=True)
kc_no_df = pd.concat([kc_no_df, y_col], axis=1)
kc_no_df
Out[193]:
In [194]:
kc_yes_df = pd.DataFrame(list(nx.common_neighbor_centrality(kc_g,kc_g.edges)),columns=['node1', 'node2','cn_cen'])
preds = nx.jaccard_coefficient(kc_g, kc_g.edges)
preds_p = []
for u, v, p in preds:
preds_p.append(p)
kc_yes_df['jaccard'] = pd.Series(preds_p)
y_col = pd.Series(1, name='HasEdge').repeat(len(kc_yes_df)).reset_index(drop=True)
kc_yes_df = pd.concat([kc_yes_df, y_col], axis=1)
kc_yes_df
Out[194]:
In [195]:
kc_lp_df = pd.concat([kc_yes_df,kc_no_df]).reset_index(drop=True)
kc_lp_df
Out[195]:
In [196]:
kc_lp_df.drop(['node1','node2'],axis=1).corr()
# common_neighbor_centrality is reasonable edge attachment sore to proxy link prediction likelihood
Out[196]:
In [197]:
fb_no_df = pd.DataFrame(list(nx.common_neighbor_centrality(FBGraph)),columns=['node1', 'node2','cn_cen'])
preds = nx.jaccard_coefficient(FBGraph)
preds_p = []
for u, v, p in preds:
preds_p.append(p)
fb_no_df['jaccard'] = pd.Series(preds_p)
y_col = pd.Series(0, name='HasEdge').repeat(len(fb_no_df)).reset_index(drop=True)
fb_no_df = pd.concat([fb_no_df, y_col], axis=1)
fb_yes_df = pd.DataFrame(list(nx.common_neighbor_centrality(FBGraph,FBGraph.edges)),columns=['node1', 'node2','cn_cen'])
preds = nx.jaccard_coefficient(FBGraph, FBGraph.edges)
preds_p = []
for u, v, p in preds:
preds_p.append(p)
fb_yes_df['jaccard'] = pd.Series(preds_p)
y_col = pd.Series(1, name='HasEdge').repeat(len(fb_yes_df)).reset_index(drop=True)
fb_yes_df = pd.concat([fb_yes_df, y_col], axis=1)
fb_lp_df = pd.concat([fb_yes_df,fb_no_df]).reset_index(drop=True)
fb_lp_df
Out[197]:
In [198]:
fb_lp_df.drop(['node1','node2'],axis=1).corr()
# common_neighbor_centrality is reasonable edge attachment sore to proxy link prediction likelihood
Out[198]:
Connectivity and clique¶
In [199]:
u_g.add_edge(5,6)
nx.draw(u_g, with_labels=True)
In [200]:
nx.is_connected(u_g)
Out[200]:
In [201]:
list(nx.connected_components(u_g))
Out[201]:
In [202]:
print(nx.is_connected(kc_g),nx.is_connected(copur_sup_g),nx.is_connected(FBGraph))
In [203]:
nx.is_strongly_connected(d_g)
Out[203]:
In [204]:
nx.is_strongly_connected(copur_conf_g)
Out[204]:
In [205]:
# Create a small graph example using add_edges_from to explore its cliques
c_g = nx.Graph()
edges = [(1,2), (1,6), (2,3), (2,4), (2,6), (3,4), (3,5), (1,3), (4,9), (6,7), (1,4), (9,10), (10,11), (9,11)]
c_g.add_edges_from(edges)
nx.draw(c_g, with_labels = True)
In [206]:
# help(nx.find_cliques)
In [207]:
list(nx.find_cliques(c_g))
Out[207]:
In [208]:
# help(nx.community.k_clique_communities)
In [209]:
list(nx.community.k_clique_communities(c_g,3))
Out[209]:
In [210]:
list(nx.community.k_clique_communities(c_g,4))
Out[210]:
In [211]:
list(nx.community.k_clique_communities(c_g,2))
Out[211]:
In [212]:
list(nx.find_cliques(kc_g))
Out[212]:
In [213]:
list(nx.community.k_clique_communities(kc_g,4))
Out[213]:
In [214]:
plt.figure(figsize=(8,8))
nx.draw(kc_g, with_labels=True)
In [215]:
list(nx.find_cliques(copur_sup_g))
Out[215]:
In [216]:
nx.draw(copur_sup_g, with_labels=True)
In [217]:
list(nx.community.k_clique_communities(copur_sup_g,3))
Out[217]:
In [218]:
list(nx.community.k_clique_communities(copur_sup_g,4))
Out[218]:
In [219]:
# list(nx.find_cliques(FBGraph))
# Run this code if you are interested in inspecting cliques in FBGraph
In [220]:
list(nx.community.k_clique_communities(FBGraph,3))
Out[220]:
In [221]:
list(nx.community.k_clique_communities(FBGraph,4))
Out[221]:
In [222]:
# help(nx.node_clique_number)
In [223]:
nx.node_clique_number(G)
Out[223]:
In [224]:
nx.node_clique_number(u_g)
Out[224]:
In [225]:
nx.node_clique_number(kc_g)
Out[225]:
In [226]:
nx.node_clique_number(copur_sup_g)
Out[226]:
In [227]:
nx.node_clique_number(FBGraph)
# Ranges from 2 to 4
Out[227]:
Isomorphism¶
In [228]:
G4 = nx.complete_graph(4)
In [229]:
G4 = nx.relabel_nodes(G4, {0:'a',1:'b',2:'c',3:'d'})
nx.draw(G4,with_labels=True)
In [230]:
nx.is_isomorphic(G,G4)
Out[230]:
In [231]:
# help(nx.graph_edit_distance)
In [232]:
nx.graph_edit_distance(G4,G)
Out[232]:
In [233]:
G5=nx.complete_graph(5)
nx.draw(G5,with_labels=True)
In [234]:
nx.graph_edit_distance(G4,G5)
Out[234]:
In [235]:
G4.edges
Out[235]:
In [236]:
G5.edges
Out[236]:
In [237]:
nx.graph_edit_distance(G,G5)
Out[237]:
In [238]:
u_g.remove_edge(5,6)
u_g.remove_node(5)
u_g.remove_node(6)
nx.draw(u_g,with_labels=True)
In [239]:
nx.graph_edit_distance(G4,u_g)
Out[239]:
In [240]:
nx.graph_edit_distance(G5,u_g)
Out[240]:
In [241]:
nx.is_isomorphic(G,u_g,edge_match=None,node_match=None)
Out[241]:
Bipartite graph¶
Import library, show graph info and drawings of bipartite graphs¶
In [242]:
import networkx.algorithms.bipartite as bipartite
In [243]:
# help(bipartite.is_bipartite)
In [244]:
# A simple example
b_g = nx.Graph()
b_g.add_nodes_from([1,2,3,4])
b_g.add_nodes_from(['a','b','c'])
b_g.add_edges_from([(1,'a'), (1,'b'), (2,'b'), (2,'c'), (3,'c'), (4,'a')])
print(nx.info(b_g),'\n')
print('The statement - b_g is a bipartitle graph is ',bipartite.is_bipartite(b_g),'\n')
nx.draw(b_g, with_labels = True)
Define a function to generate a dataframe of a undirected graph¶
In [245]:
def undirected_graph_metric_df(g):
g_df = pd.DataFrame(index=g.nodes())
g_df['degree'] = pd.Series(dict(g.degree()))
g_df['eccentricity'] = pd.Series(nx.eccentricity(g))
g_df['clustering'] = pd.Series(nx.clustering(g))
g_df['degree_centrality'] = pd.Series(nx.degree_centrality(g))
g_df['closeness'] = pd.Series(nx.closeness_centrality(g))
g_df['betweenness'] = pd.Series(nx.betweenness_centrality(g))
return g_df
In [246]:
# Many of the undirected graph functions can be applied to nodes of two types
b_df = undirected_graph_metric_df(b_g)
b_df
Out[246]:
Create two sets of nodes based on types¶
In [247]:
#help(nx.bipartite.sets)
In [248]:
l, r = nx.bipartite.sets(b_g)
print('set l:',l,'\n')
print('set r:',r)
show biadjacency_matrix¶
In [249]:
# help(bipartite.biadjacency_matrix)
In [250]:
print("Biadjacency matrix")
print(bipartite.biadjacency_matrix(b_g, l, r).todense())
Align nodes of the same type for using nx.draw()¶
In [251]:
# help(enumerate)
In [252]:
for set_index, node_label in enumerate(l):
print(set_index,node_label)
In [253]:
for set_index, node_label in enumerate(r):
print(set_index,node_label)
In [254]:
# create a customized node layout dictionary - pos1
pos1 = {}
# Update position for drawing with a bipartite group number
# Use update to update the content of pos1
pos1.update((node_label, (1,set_index)) for set_index, node_label in enumerate(l))
pos1.update((node_label, (2,set_index)) for set_index, node_label in enumerate(r))
pos1
Out[254]:
In [255]:
# Align drawing of nodes by node type using the customized node layout dictionary
nx.draw(b_g, pos=pos1, with_labels = True)
Davis woman club graph¶
In [256]:
davis_g = nx.davis_southern_women_graph()
print(nx.info(davis_g),'\n')
print('The statement - davis_g is a bipartitle graph is ',bipartite.is_bipartite(davis_g),'\n')
plt.figure(figsize=(12,12))
nx.draw_circular(davis_g, with_labels=True)
In [257]:
dvs_df = undirected_graph_metric_df(davis_g)
dvs_df
Out[257]:
In [258]:
women_set, clubs_set = nx.bipartite.sets(davis_g)
In [259]:
women_set
Out[259]:
In [260]:
clubs_set
Out[260]:
In [261]:
print(bipartite.biadjacency_matrix(davis_g, women_set, clubs_set).todense())
In [262]:
# print degree information
h1 = 'Member'
h2 = 'Number of Clubs'
print(f'{h1:25} {h2:10}\n')
for w in women_set:
print(f"{w:25} {davis_g.degree(w):10}")
h3 = 'Club'
h4 = 'Number of Members'
print('\n', f'{h3:25} {h4:10}\n')
for w in clubs_set:
print(f"{w:25} {davis_g.degree(w):10}")
In [263]:
pos_davis = {}
# Update position for node from each group
pos_davis.update((node, (1, index)) for index, node in enumerate(clubs_set))
pos_davis.update((node, (2, index)) for index, node in enumerate(women_set))
plt.figure(figsize=(10,10))
nx.draw(davis_g, pos = pos_davis, with_labels=True)
plt.show()
Project a bipartite graph onto an undirected graph of a single type of nodes¶
In [264]:
# help(bipartite.projected_graph)
In [265]:
women_g = bipartite.projected_graph(davis_g, women_set)
print(nx.info(women_g),'\n')
print('The statement - women_g is a bipartitle graph is ',bipartite.is_bipartite(women_g),'\n')
plt.figure(figsize=(10,10))
nx.draw_circular(women_g, with_labels=True)
In [266]:
women_df = undirected_graph_metric_df(women_g)
women_df
Out[266]:
In [267]:
women_df.corr()
Out[267]:
In [268]:
clubs_g = bipartite.projected_graph(davis_g, clubs_set)
print(nx.info(clubs_g),'\n')
print('The statement - clubs_g is a bipartitle graph is ',bipartite.is_bipartite(clubs_g),'\n')
plt.figure(figsize=(6,6))
nx.draw_circular(clubs_g, with_labels=True)
In [269]:
clubs_df = undirected_graph_metric_df(clubs_g)
clubs_df
Out[269]:
In [270]:
clubs_df.corr()
Out[270]:
Project a bipartite graph onto a weighted graph¶
In [271]:
# help(bipartite.weighted_projected_graph)
In [272]:
women_wg = bipartite.weighted_projected_graph(davis_g, women_set)
print(nx.info(women_wg),'\n')
print('The statement - women_wg is a bipartitle graph is ',bipartite.is_bipartite(women_wg),'\n')
plt.figure(figsize=(10,10))
comm_clubs =[(women_wg[u][v]['weight']) for u,v in women_wg.edges]
nx.draw_circular(women_wg, width=comm_clubs,edge_color = 'orange',with_labels=True)
In [273]:
women_w_edge_df = pd.DataFrame(list(women_wg.edges.data('weight')))
women_w_edge_df
Out[273]:
In [274]:
clubs_wg = bipartite.weighted_projected_graph(davis_g, clubs_set)
print(nx.info(clubs_wg),'\n')
print('The statement - clubs_wg is a bipartitle graph is ',bipartite.is_bipartite(clubs_wg),'\n')
plt.figure(figsize=(6,6))
comm_members =[clubs_wg[u][v]['weight'] for u,v in clubs_wg.edges]
nx.draw_circular(clubs_wg, width=comm_members,edge_color = 'purple',with_labels=True)
In [275]:
clubs_w_edge_df = pd.DataFrame(list(clubs_wg.edges.data('weight')))
clubs_w_edge_df
Out[275]:
Watts–Strogatz small-world graph¶
In [276]:
# help(nx.watts_strogatz_graph)
In [277]:
sw_g1 = nx.watts_strogatz_graph(100,2,0.0)
print(nx.info(sw_g1))
plt.figure(figsize=(10,10))
nx.draw_circular(sw_g1)
In [278]:
sw_g2 = nx.watts_strogatz_graph(100,8,0.2)
print(nx.info(sw_g2))
plt.figure(figsize=(10,10))
nx.draw_circular(sw_g2)
In [279]:
sw_df2 = undirected_graph_metric_df(sw_g2)
sw_df2
Out[279]:
In [280]:
sw_df2.corr()
Out[280]:
In [281]:
sw_g3 = nx.watts_strogatz_graph(100,8,0.8)
print(nx.info(sw_g3))
plt.figure(figsize=(10,10))
nx.draw_circular(sw_g3)
In [282]:
sw_df3 = undirected_graph_metric_df(sw_g3)
sw_df3
Out[282]:
In [283]:
sw_df3.corr()
Out[283]:
In [284]:
sw_g4 = nx.watts_strogatz_graph(100,8,0.4)
print(nx.info(sw_g4))
plt.figure(figsize=(10,10))
nx.draw_circular(sw_g4)
In [285]:
sw_df4 = undirected_graph_metric_df(sw_g4)
sw_df4
Out[285]:
In [286]:
sw_df4.corr()
Out[286]:
A real world example can be social media follower- following relationship.The graph of the relationships (followed/follower) betweens the users, (so we need the relation_user data) but we are also interested about the credibility of each user (so we need the newsUser and labels_training sets).
The resource for this example is: https://www.kaggle.com/adoury/web-mining-project-web-mining-analysis
Generate hmtl output file of this notebook¶
In [289]:
# Enter and run the following lines of commands in your notebook to generate
# an hmtl file of your notebook with NbConvertApp
# copy the ipynb to the local working directory using ! to run a shell command,
# cp, to copy my notebook in a folder named "Colab Notebooks"
# to a local working directory referenced via ./
!cp "/content/drive/My Drive/Colab Notebooks/Copy of Graph Mining.ipynb" ./
# run the second shell command, jupyter nbconvert --to html "file name of the notebook"
# create html from ipynb
!jupyter nbconvert --to html "Graph Mining.ipynb"